In the field of PDU switching, a switching device 10 (see FIG. 1) of a data switching node 12 transfers Payload Data Units (PDU) from input ports 20 carrying data traffic flows 22, generally referred to as the input, to the output which has associated therewith a plurality of output ports 30 carrying data traffic flows 32. Examples of PDUs include: packets, cells, frames but not limited thereto.
In order to provide Quality-of-Service (QoS) guarantees, a Class-of-Service (CoS) is associated to each PDU and data traffic flow 32. PDUs having the same CoS and destined for a particular output port 30, are aggregated into a single data flow 32. PDUs 106 associated with a single data flow 32 are queued in a corresponding output queue Q(j) for transmission over a physical medium 102 of the output port 30. Each one of m output queues Q(j) associated with the output port 30 may be implemented in hardware or software and is ascribed at least a transmission bandwidth and priority in relation to other data traffic flows 32 destined for the output port 30. As such, a high priority PDU associated with a voice connection may await in an output queue Q(m−1) having a high service priority associated therewith while a low priority PDU associated with an electronic mail transfers session may await in an output queue Q(0) having a low service priority associated therewith.
The selection of PDUs 106 for transmission over the physical medium is made by a scheduler 40. In providing QoS guarantees it is generally required that high priority PDUs receive a guaranteed fraction of the transmission bandwidth. Therefore high priority PDUs benefit from preferential processing thereof.
Due to a varying length 110 of the PDUs conveyed, all data traffic flows 32 become subject to transmission delay and transmission jitter. It is considered desirable for low transmission priority output queues to receive some guaranteed fraction of bandwidth so as not to completely be blacked out during periods of data traffic bursts of high priority PDUs. To implement CoS and to achieve low transmission delays and jitter, an enforcer 50 is used in queuing PDUs in the output queues Q(j) ensuring that not too many high priority PDUs 106 are queued for transmission during an interval of time.
Several theoretical models have been developed to partition the transport bandwidth of the output physical medium 102 among the output queues Q(j) implementing Weighted Fair Queuing (WFQ) techniques. One such technique is described by Srinivasan Keshav in “An Engineering Approach to Computer Networking: ATM Networks, the Internet, and the Telephone Network” published by Addison Wesley, 1997, Reading Mass., pp 209–263.
WFQ techniques provide a solution to the problem of bandwidth partitioning while being considered impractical to implement in hardware. Theoretical queue servicing models typically assume that the computational time spent implementing WFQ is infinitesimal and therefore ignored. In practice the computational time can not be ignored. WFQ techniques use iterative calculations in sequencing output queue servicing. Iterative calculations are time intensive. WFQ sequencing calculations also require division operations which represent sources of great implementation complexity in hardware.
There therefore is a need to develop methods to sequence output queue servicing in a manner that emulates weighted fair queuing techniques while overcoming the above presented shortcomings.